package com.ryujung.array.leetCode_42;

/*Leecode算法42题.接雨滴

	由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水
		输入: [0,1,0,2,1,0,1,3,2,1,2,1]
		输出: 6
*/
public class Solution {
    /*
    解法一:
        思路:
            遍历所有的索引,找出其左侧最高水位max_l和右侧最高水位max_r,
            取其中最小值min(max_l,max_r),
            索引0和索引height.length-1除外(不能接到雨滴)
            用最小值再减去当前索引位的水位高度,就是当前索引为能接的雨滴数
        解题步骤:
            1.定义int变量累加可接受的雨滴总数
            2.for循环遍历高度图,计算每个索引的接雨滴数
        时间复杂度:O(n^2),数组中每个数都要扫描左右两边
    */
    public int trap1(int[] height) {
        //定义int变量累加可接受的雨滴总数
        int count = 0;
        int max_l, max_r;

        //for循环遍历高度图,计算每个索引的接雨滴数
        for (int i = 0; i < height.length; i++) {
            max_l = 0;
            max_r = 0;
            for (int x = 0; x < i; x++) {
                max_l = Math.max(max_l, height[x]);
            }
            for (int y = i; y < height.length; y++) {
                max_r = Math.max(max_r, height[y]);
            }

            //左右两侧最大值中相对小的数减去当前索引的高度,就是该索引可以接的雨滴数
            count += Math.max((Math.min(max_l, max_r) - height[i]), 0);
        }
        return count;
    }

    /*
    方法二:
        思路:
            为了获取每个索引位的可接水滴数,需要三个参数:该索引左侧的最大高度max_l,右侧的最大高度max_r,该索引的高度height[i]
            定义两个数组,长度均为height.length,分别存储每个索引对应的max_l,max_r(1~height.length-2)
            计算每个索引能接收雨滴的数量res += min(max_r,max_l)-height[i]
     */
    public int trap2(int[] height) {
        int count = 0;
        int len = height.length;
        int[] max_l = new int[len];
        int[] max_r = new int[len];
        max_l[0] = height[0];
        max_r[len - 1] = height[len - 1];
        for (int i = 1; i < len; i++) {
            max_l[i] = Math.max(max_l[i - 1], height[i]);
        }
        for (int i = len - 2; i >= 0; i--) {
            max_r[i] = Math.max(max_r[i + 1], height[i]);
            count += Math.min(max_l[i], max_r[i]) - height[i];
        }
        return count;
    }

    public int trap3(int[] height) {
        int count = 0;
        int len = height.length;
        int max_l = 0, max_r = 0;
        int left = 0, right = len - 1;
        while (left < right) {
            if (max_l > max_r) {
                count += max_r - height[left + 1];
            } else {

            }
        }

        return count;
    }
}
